package main

import (
	"fmt"
)

/**
执行用时：8 ms, 在所有 Go 提交中击败了77.24%的用户
内存消耗：4.3 MB, 在所有 Go 提交中击败了62.05%的用户
 */
func minPathSum(grid [][]int) int {

	n, m := len(grid), len(grid[0])
	f := make([][]int, n)
	for i := 0; i < n; i++ {
		f[i] = make([]int, m)
		for j := 0; j < m; j++ { f[i][j] = INT_MAX }
	}

	for i := 0; i < n; i++ {
		for j := 0; j < m; j++ {
			if i == 0 && j == 0 {
				f[i][j] = grid[i][j]
			} else {
				if i > 0 { f[i][j] = min(f[i][j], f[i - 1][j] + grid[i][j]) }
				if j > 0 { f[i][j] = min(f[i][j], f[i][j - 1] + grid[i][j]) }
			}
		}
	}
	return f[n - 1][m - 1]
}

const INT_MAX = (1 << 31) - 1

// 求最小值
func min(a int, b int) int {
	if a > b {
		return b
	} else {
		return a
	}
}

func main() {

	grid := [][]int{{1, 2}, {1, 1},}
	fmt.Println(minPathSum(grid))  // 3
}
